package com.wtx.chapter08;

import java.util.Arrays;

/**
 * @description: Floyed 算法: 用于求解加权连通图的 完全最短路径的问题, 即任意两个顶点的距离
 * @author: wtx
 * @createDate: 2020/6/10
 */
public class Floyed {

    // graph: 图, 数值为权值, 没有边使用-1表示
    public static int[][] solution(int[][] graph){

        int[][] res = graph;
        for (int k = 0; k < graph.length; k++)
            for (int i = 0; i < graph.length; i++)
                for (int j = 0; j < graph.length; j++)
                    if (res[i][k]!=Integer.MAX_VALUE && res[k][j]!=Integer.MAX_VALUE)
                        res[i][j] = Math.min(res[i][j], res[i][k]+res[k][j]);

        return res;
    }

    public static void main(String[] args) {

        int[][] graph = new int[4][4];
        for (int i = 0; i < graph.length; i++){
            Arrays.fill(graph[i],Integer.MAX_VALUE);
            graph[i][i] = 0;
        }
        graph[0][2] = 3;
        graph[1][0] = 2;
        graph[2][1] = 7;
        graph[2][3] = 1;
        graph[3][0] = 6;

        int[][] solution = Floyed.solution(graph);
        for (int i = 0; i < graph.length; i++) {
            for (int j = 0; j < graph.length; j++)
                System.out.print(solution[i][j]+"  ");
            System.out.println();
        }
    }
}
